<?php

/**
 * 接雨水
 * Class Solution
 */
class Solution {

    /**
     * @param Integer[] $height
     * @return Integer
     */
    function trap($height) {
        arsort($height);
        $sum=0;

        $rangeArr=[-1,-1];
        foreach($height as $index=>$h){
            if($rangeArr[0]<0){
                $rangeArr[0]=$index;
                continue;
            }elseif($rangeArr[1]<0){
                $rangeArr[1]=$index;
                if($rangeArr[0]>$rangeArr[1]){
                    $tmp=$rangeArr[0];
                    $rangeArr[0]=$rangeArr[1];
                    $rangeArr[1]=$tmp;
                }
                $sum+=$this->calcSum($height,$rangeArr[0],$rangeArr[1]);
            }elseif($index<$rangeArr[0]){
                $sum+=$this->calcSum($height,$index,$rangeArr[0]);
                $rangeArr[0]=$index;
            }elseif($index>$rangeArr[1]){
                $sum+=$this->calcSum($height,$rangeArr[1],$index);
                $rangeArr[1]=$index;
            }
        }
        return $sum;
    }

    function calcSum($height,$startIndex,$endIndex){
        //交换位置，确保 startIndex<endIndex
        if($startIndex>$endIndex){
            $tmp=$startIndex;
            $startIndex=$endIndex;
            $endIndex=$tmp;
        }
//        dump("计算{$startIndex}-{$endIndex}");

        $startH=$height[$startIndex];
        $endH=$height[$endIndex];
        $minH=$startH>$endH?$endH:$startH;
        $sum=$minH*($endIndex-$startIndex-1);
        for($i=$startIndex+1;$i<$endIndex;$i++){
            $h=$height[$i];
            $h>$minH && $h=$minH;
            $sum-=$h;
        }
        return $sum;
    }
}